	<!DOCTYPE html>
<html lang="zh-Hans">
	<head>
		<!--[if lt IE 9]>
        	<style>body {display: none; background: none !important} </style>
        	<meta http-equiv="Refresh" Content="0; url=//outdatedbrowser.com/" />
    	<![endif]-->

		<meta charset="utf-8">
		<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1" />
		<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
		<meta name="format-detection" content="telephone=no" />
		<meta name="author" content="Shawn" />
		

		<link rel="apple-touch-icon" href="http://og6esej9r.bkt.clouddn.com/me-0.JPG">
		<link rel="alternate" href="/atom.xml" title="诗酒趁年华" type="application/atom+xml">
		<link rel="shortcut icon" href="/img/me.JPG">
		<link href="//cdn.bootcss.com/animate.css/3.5.1/animate.min.css" rel="stylesheet">
		<link href="//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.css" rel="stylesheet">
		<script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script>
    	<link href="//cdn.bootcss.com/pace/1.0.2/themes/blue/pace-theme-loading-bar.css" rel="stylesheet">
		<link rel="stylesheet" href="/css/style.css">
		
		

		<link href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet">
		
		<title>编译原理——语言及其文法 | 诗酒趁年华</title>

		<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
		<script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>
		<!--<script src="/js/huaji.js"></script>-->
		
		<script src="/js/APlayer.min.js"></script>
		<script src="/js/canvas.js"></script>
  		<script src="/js/leftmusic.js"></script>
  		<script src="/js/jquery.marquee.min.js"></script>
  		<script src="//code.jquery.com/jquery-migrate-1.2.1.min.js"></script>
		
		 
		<!-- Live2D Library -->
        <script src="/js/live2d.min.js"></script>        
        <!-- Live2D Framework -->
        <script src="/js/Live2DFramework.js"></script>
        <!-- User's Script -->
    	<script src="/js/utils/MatrixStack.js"></script>
        <script src="/js/utils/ModelSettingJson.js"></script>
        <script src="/js/PlatformManager.js"></script>
        <script src="/js/LAppDefine.js"></script>
        <script src="/js/LAppModel.js"></script>
        <script src="/js/LAppLive2DManager.js"></script>
        <script src="/js/22.js"></script>	
         		        
	
		<script>
  			var yiliaConfig = {
     	   		fancybox: true,
        		animate: true,
        		isHome: false,
        		isPost: true,
        		isArchive: false,
        		isTag: false,
        		isCategory: false,
        		fancybox_js: "//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.js",
        		scrollreveal: "//cdn.bootcss.com/scrollReveal.js/3.1.4/scrollreveal.min.js",
        		search: true
    		}
		</script>
		
		
		
		<script>
        	yiliaConfig.jquery_ui = [true, "//cdn.bootcss.com/jqueryui/1.10.4/jquery-ui.min.js", "//cdn.bootcss.com/jqueryui/1.10.4/css/jquery-ui.min.css"];
    	</script>
		

		<script> yiliaConfig.rootUrl = "\/";</script>	
		

		
	</head>

	 
		<body onload="ThisIs22()">
	
  		<div id="container">
    		<div class="left-col">
    			<div class="overlay"></div>
    			<div class="intrude-less">
	    			<header id="header" class="inner">
            			<a href="/" class="profilepic">
                			<img src="/img/me.JPG" class="animated zoomIn">
            			</a>
            			<hgroup>
              				<h1 class="header-author" style="width:100%"><a href="/">Shawn</a></h1>
            			</hgroup>
            			<p class="header-subtitle">一个喜欢捣鼓前端的产品汪。<br/>总字数：<span class="post-count" style="font-weight: bold;font-family: Arial, Helvetica, "宋体";color: black;">17.8k</span></p>

            			<form id="search-form"> <!-- 搜索框相关 -->
    			    		<input type="text" id="local-search-input" name="q" results="0" placeholder="" class="search form-control" autocomplete="off" autocorrect="off"/>
   				    		<i class="fa fa-times" onclick="resetSearch()"></i> <!-- 清空/重置搜索框 -->
			    		</form>
			    		<div id="local-search-result"></div> <!-- 搜索结果区 -->
			    		<p class='no-result'>啊哦。。。<br/>没有符合条件的文章。。。<br/>∠( ᐛ 」∠)＿</p> <!-- 无匹配时显示，注意请在 CSS 中设置默认隐藏 -->
            			
            			<div id="switch-area" class="switch-area">
    			            <div class="switch-wrap">
    			                <section class="switch-part switch-part1">
    			                    <nav class="header-menu">
    			                    	<a href="/" title="回到首页"><i class="fa fa-home"></i></a>
    			                    	<a href="/archives/" title="文章归档"><i class="fa fa-archives"></i></a>
    			                    	<a href="/tags/" title="标签/分类"><i class="fa fa-tags"></i></a>
    			                    	<a href="/photoes/" title="照片/壁纸"><i class="fa fa-photo"></i></a>
    			                    	<a href="/friends/" title="友情链接"><i class="fa fa-links"></i></a>
    			                    	<a href="/about/" title="关于我/留言板"><i class="fa fa-about"></i></a>
    			                    	<a href="/download/" title="相关下载"><i class="fa fa-download"></i></a>
    									<a class="set-view-mode" href="javascript:void(0)" title="夜间模式"><i class="fa fa-moon-o"></i></a>
    			                    </nav>
    			                </section>   
    			                <section class="switch-part switch-part2">
    			                    <div class="widget tagcloud" id="js-tagcloud">
    			                        <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/2017/">2017</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/CDN/">CDN</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/DFS/">DFS</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Github/">Github</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/HTML5/">HTML5</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Hexo/">Hexo</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/JavaScript/">JavaScript</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/PS/">PS</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/SSL/">SSL</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/flag/">flag</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/https/">https</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/localStorage/">localStorage</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/nginx/">nginx</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sessionStorage/">sessionStorage</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/夜间模式/">夜间模式</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/影评/">影评</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/文档/">文档</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/服务学/">服务学</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/编译原理/">编译原理</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/随笔/">随笔</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/项目管理/">项目管理</a></li></ul>
    			                    </div>
    			                </section>
    			                
    			                            
 			            	</div>
 			            	<div class="marquee"><script type="text/javascript" src="https://api.lwl12.com/hitokoto/main/get?encode=js&charset=utf-8"></script><div id="lwlhitokoto"><script>lwlhitokoto()</script></div></div><script>$('.marquee').marquee();</script>
    			        </div>
    			    </header>   
    			</div>
    			       
    		</div>
    		 
    			<script src="//cdn.bootcss.com/jqueryui/1.10.4/jquery-ui.min.js"></script>
    			<script src="/js/move.js"></script>
    			<div id="movediv"> 
        			<canvas id="glcanvas" width="170" height="200"> <button id="btnChange" class="active" style="visibility:hidden;width=10px!important;">C</button></canvas>
    			</div>
    		
    		<div class="xm"><img src="/img/xm.png"></div>
    		<div class="mid-col">
    			<nav id="mobile-nav">
      <div class="overlay">
          <div class="slider-trigger"></div>
          <h1 class="header-author js-mobile-header hide"><a href="/" title="回到主页">Shawn</a></h1>
      </div>
    <div class="intrude-less">
        <header id="header" class="inner">
            <a href="/" class="profilepic">
                <img src="/img/me.JPG" class="animated zoomIn">
            </a>
            <hgroup>
              <h1 class="header-author"><a href="/" title="回到主页">Shawn</a></h1>
            </hgroup>
            
            <p class="header-subtitle"><span class="post-count">一个喜欢捣鼓前端的产品汪。<br/>总字数：17.8k</span></p>
            
            <nav class="header-menu">
            	<div>
    			<a href="/" title="回到首页"><i class="fa fa-home"></i></a>
    			<a href="/archives/" title="文章归档"><i class="fa fa-archives"></i></a>
    			<a href="/tags/" title="标签/分类"><i class="fa fa-tags"></i></a>
    			<a href="/photoes/" title="照片/壁纸"><i class="fa fa-photo"></i></a>
    			<a href="/friends/" title="友情链接"><i class="fa fa-links"></i></a>
    			</div>
    			<div>
    			<a href="/about/" title="关于我/留言板"><i class="fa fa-about"></i></a>
    			<a href="/download/" title="相关下载"><i class="fa fa-download"></i></a>
    			<a class="set-view-mode" href="javascript:void(0)" title="夜间模式"><i class="fa fa-moon-o"></i></a>
    			</div>
    		</nav><br/><br/><br/>
        </header>                
    </div>
    <link class="menu-list" tags="标签" friends="友情链接" about="关于我"/>
</nav>
      			<div class="body-wrap"><article id="post-Compile02" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/2016/11/30/Compile02/" class="article-date">
      <time datetime="2016-11-30T07:44:36.000Z" itemprop="datePublished">2016-11-30</time>
</a>


    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      		编译原理——语言及其文法
    </h1>
  

      </header>
      
      <div class="article-info article-info-post">
        
    <div class="article-category tagcloud">
    <a class="article-category-link" href="/categories/学习/">学习</a>
    </div>


        
    <div class="article-tag tagcloud">
        <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/编译原理/">编译原理</a></li></ul>
    </div>

        <div class="clearfix"></div>
      </div>
      
    
    <div class="article-entry" itemprop="articleBody">
      
          
        <h2 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h2><h3 id="字母表"><a href="#字母表" class="headerlink" title="字母表"></a>字母表</h3><p><span class="suojin"></span>字母表$\Sigma$是一个<code>有穷符号集合</code>。符号的典型例子包括<code>字母</code>、<code>数字</code>和<code>标点符号</code>。<br>例：  </p>
<ul>
<li>二进制字母表：$\lbrace 0,1\rbrace$</li>
<li>$ASCII$</li>
<li>$Unicode$</li>
</ul>
<a id="more"></a>
<h4 id="字母表上的运算"><a href="#字母表上的运算" class="headerlink" title="字母表上的运算"></a>字母表上的运算</h4><p><span class="suojin"></span>字母表$\Sigma_1$和$\Sigma_2$的<code>乘积</code>($product$)<br>$$\Sigma_1 \Sigma_2 = \lbrace ab \mid a \in \Sigma_1, b \in \Sigma_2 \rbrace$$</p>
<hr>
<p><span class="suojin"></span>字母表$\Sigma$的<code>n次幂</code>($power$)<br>$$<br>\begin{cases}<br>\Sigma^0=\lbrace\epsilon\rbrace\\<br>\Sigma^n=\Sigma^{n-1}\Sigma, &amp; n \geqslant 1<br>\end{cases}<br>$$<br>例：$\lbrace0,1\rbrace^3 = \lbrace 0,1\rbrace \lbrace0, 1\rbrace \lbrace0, 1\rbrace<br>=\lbrace000,001,010,011,100,101,110,111\rbrace$  </p>
<blockquote>
<p>字母表的$n$次幂：长度为$n$的符号串构成的集合 </p>
</blockquote>
<hr>
<p><span class="suojin"></span>字母表$\Sigma$的<code>正闭包</code>($positive\ closure$)<br>$$<br>\Sigma^{+}=\Sigma\cup\Sigma^2\cup\Sigma^3\cup…<br>$$</p>
<blockquote>
<p>字母表的正闭包：长度正数的符号串构成的集合</p>
</blockquote>
<hr>
<p><span class="suojin"></span>字母表∑的<code>克林闭包</code>($Kleene\ closure$)</p>
<p>$$<br>\Sigma^{*}=\Sigma\cup\Sigma^{+}=\Sigma^0\cup\Sigma^1\cup\Sigma^2\cup\Sigma^3\cup…<br>$$</p>
<blockquote>
<p>字母表的克林闭包：任意符号串（长度可以为零）构成的集合</p>
</blockquote>
<hr>
<h3 id="串"><a href="#串" class="headerlink" title="串"></a>串</h3><p><span class="suojin"></span>设$\Sigma$是一个字母表，$\forall x\in \Sigma^{*}$，$x$称为是$\Sigma$上的一个<code>串</code></p>
<blockquote>
<p>串是字母表中符号的一个有穷序列</p>
</blockquote>
<p><span class="suojin"></span>串$s$的<code>长度</code>，通常记作$\mid\ s\ \mid$，是指$s$中符号的个数<br>例：$$\mid\ aab\mid =3$$<br><code>空串</code>是<code>长度为0的串</code>，用$\epsilon$($epsilon$)表示<br>$$\mid\ \epsilon\mid =0$$</p>
<h3 id="串上的运算"><a href="#串上的运算" class="headerlink" title="串上的运算"></a>串上的运算</h3><p><span class="suojin"></span>如果$x$和$y$是串，那么$x$和$y$的<code>连接</code>($concatenation$)是把$y$附加到$x$后面而形成的串，记作$xy$。  </p>
<ul>
<li>例如，如果$x = dog$且$y = house$，那么$xy = doghouse$。  </li>
<li>空串是连接运算的单位元($identity$)，即，对于任何串$s$都有，$\epsilon s = s\epsilon = s$。  </li>
<li>设$x,y,z$是三个字符串，如果$x=yz$，则称$y$是$x$的<code>前缀</code>，$z$是$x$的<code>后缀</code>。</li>
</ul>
<p><span class="suojin"></span>串$s$的<code>幂</code>运算<br>$$<br>\begin{cases}<br>s^0=\epsilon\\<br>s^n=s^{n-1}s, &amp; n \geqslant 1<br>\end{cases}<br>$$</p>
<blockquote>
<p>串$s$的$n$次幂：将$n$个$s$连接起来</p>
</blockquote>
<ul>
<li>$s^1=s^0s=\epsilon s,s^1=ss,s^3=sss,…$</li>
<li>例：如果$s=ba$,那么$s^1=ba,s^2=baba,s^3=bababa,…$</li>
</ul>
<h2 id="文法的定义"><a href="#文法的定义" class="headerlink" title="文法的定义"></a>文法的定义</h2><p><span class="suojin"></span>自然语言的例子——<code>句子的构成规则</code></p>
<ul>
<li>&lt;句子&gt;$\rightarrow$&lt;名词短语&gt;&lt;动词短语&gt;</li>
<li>&lt;名词短语&gt;$\rightarrow$&lt;形容词&gt;&lt;名词短语&gt;</li>
<li>&lt;名词短语&gt;$\rightarrow$&lt;名词&gt; </li>
<li>&lt;动词短语&gt;$\rightarrow$&lt;动词&gt;&lt;名词短语&gt;</li>
<li>&lt;形容词&gt;$\rightarrow little$</li>
<li>&lt;名词&gt;$\rightarrow boy$</li>
<li>&lt;名词&gt;$\rightarrow apple$</li>
<li>&lt;动词&gt;$\rightarrow eat$</li>
</ul>
<h3 id="文法的形式化定义"><a href="#文法的形式化定义" class="headerlink" title="文法的形式化定义"></a>文法的形式化定义</h3><p>$G=(V_T,V_N,P,S)$</p>
<ul>
<li>$V_T$：终结符集合<ul>
<li><code>终结符</code>($terminal\ symbol$)是文法所定义的语言的<code>基本符号</code>，有时也称为$token$</li>
<li>例: $V_T = \lbrace apple, boy, eat, little \rbrace$</li>
</ul>
</li>
<li>$V_N$：非终结符集合<ul>
<li><code>非终结符</code>($nonterminal$)是用来表示语法成分的符号，有时也称为“语法变量”</li>
<li>例: $V_N = \lbrace $句子,名词短语,动词短语,名词,动词,形容词,…$\rbrace$</li>
</ul>
</li>
<li>$P$:产生式集合<ul>
<li>产生式($production$)描述了将终结符和非终结符组合成串的方法</li>
<li>产生式的一般形式：$\alpha\rightarrow\beta$,读作：$\alpha$定义为$\beta$</li>
<li>$\alpha \in(V_T\cup V_N)^+$，且$\alpha$中至少包含$V_N$中的一个元素：称为产生使的头($head$)或左部($left\ side$)</li>
<li>$\beta \in(V_T\cup V_N)^{*}$：称为产生使的体($body$)或右部($right\ side$)</li>
<li>例：$P=\lbrace$&lt;句子&gt;$\rightarrow$&lt;名词短语&gt;&lt;动词短语&gt;,…$\rbrace$</li>
</ul>
</li>
<li>$S$：开始符号<ul>
<li>$S\in V_N$。<code>开始符号</code>($start\ symbol$)表示的是该文法中最大的语法成分</li>
<li>例：$S = $&lt;句子&gt;</li>
</ul>
</li>
</ul>
<blockquote>
<p>$V_T\cap V_N=\phi$<br>$V_T\cup V_N=$文法符号集<br>约定：不引起歧义的前提下，可以只写产生式<br>例：<br>$G=(\lbrace id,+,*,(,)\rbrace,\lbrace E\rbrace,P,E)$<br>$P=\lbrace E\rightarrow E+E,E\rightarrow E*E,$<br>$E\rightarrow (E),E\rightarrow id\rbrace$<br>可以简写成：<br>$G:E\rightarrow E+E$<br>$\ \ \ \ \ \ \ E\rightarrow E*E$<br>$\ \ \ \ \ \ \ E\rightarrow (E)$<br>$\ \ \ \ \ \ \ E\rightarrow id$  </p>
</blockquote>
<h3 id="产生式的简写"><a href="#产生式的简写" class="headerlink" title="产生式的简写"></a>产生式的简写</h3><p><span class="suojin"></span>对一组有<code>相同左部</code>的$\alpha$产生式<br>$$\alpha\rightarrow\beta_1,\alpha\rightarrow\beta_2,…,\alpha\rightarrow\beta_n$$<br>可以简记为：<br>$$\alpha\rightarrow\beta_1\mid\beta_2\mid …\beta_n$$<br>读作：$\alpha$<code>定义为</code>$\beta_1$，或者$\beta_2$，…，或者$\beta_n$<br>$\beta_1,\beta_2,…,\beta_n$称为$\alpha$的<code>候选式</code>($Candidate$)<br>例：<br>$$<br>E\rightarrow E+E\\<br>E\rightarrow E*E\\<br>E\rightarrow (E)\\<br>E\rightarrow id<br>$$<br>可以转化为：<br>$$E\rightarrow E+E\mid E*E\mid (E)\mid id$$</p>
<h3 id="符号约定"><a href="#符号约定" class="headerlink" title="符号约定"></a>符号约定</h3><ul>
<li>下述符号是<code>终结符</code><ul>
<li>字母表中<code>排在前面的小写字母</code>，如$a,b,c$</li>
<li><code>运算符</code>，如$+,*$等</li>
<li><code>标点符号</code>，如括号、逗号等</li>
<li><code>数字</code>，$0,1,…,9$</li>
<li><code>粗体字符串</code>，如$id,if$等</li>
</ul>
</li>
<li>下述符号是<code>非终结符</code><ul>
<li>字母表中<code>排在前面的大写字母</code>，如$A,B,C$</li>
<li>字母$S$。通常表示开始符号</li>
<li><code>小写、斜体的名字</code>，如$expr,stmt$等</li>
<li><code>代表程序构造的大写字母</code>。如$E$(表达式)、$T$(项)和$F$(因子)</li>
</ul>
</li>
<li>字母表中<code>排在后面的大写字母</code>（如$X,Y,Z$）表示<code>文法符号</code>（即终结符或非终结符）</li>
<li>字母表中<code>排在后面的小写字母</code>（主要是$u,v,…,z$）表示<code>终结符号串</code>（包括<code>空串</code>）</li>
<li><code>小写希腊字母</code>，如$\alpha,\beta,\gamma$，表示<code>文法符号串</code>（包括<code>空串</code>）</li>
<li>除非特别说明，<code>第一个产生式的左部</code>就是<code>开始符号</code></li>
</ul>
<h2 id="语言的定义"><a href="#语言的定义" class="headerlink" title="语言的定义"></a>语言的定义</h2><p><span class="suojin"></span>有了文法（语言规则），如何判定一个词串是否是满足文法的句子？  </p>
<h3 id="推导-Derivations-和归约-Reductions"><a href="#推导-Derivations-和归约-Reductions" class="headerlink" title="推导($Derivations$)和归约($Reductions$)"></a>推导($Derivations$)和归约($Reductions$)</h3><p><span class="suojin"></span>给定文法$G=(V_T,V_N,P,S)$，如果$\alpha\rightarrow\beta\in P$，那么可以将符号串$\gamma\alpha\delta$中的$\alpha$替换为$\beta$，也就是说，将$\gamma\alpha\delta$重写($rewrite$)为$\gamma\beta\delta$，记作$\gamma\alpha\delta\Rightarrow\gamma\beta\delta$。此时，称文法中的符号串$\gamma\alpha\delta$<code>直接推导</code>($directly derive$)出$\gamma\beta\delta$。<br><span class="suojin"></span>简而言之，就是用产生式的右部<code>替换</code>产生式的左部。</p>
<p><span class="suojin"></span>如果$\alpha_1\Rightarrow\alpha_2,\alpha_2\Rightarrow\alpha_3,…,\alpha_{n-1}\Rightarrow\alpha_n$，则可以记作$\alpha_1\Rightarrow\alpha_2\Rightarrow\alpha_3\Rightarrow …\Rightarrow\alpha_n$，称符号串$\alpha_1$经过$n$步推导出$\alpha_n$，可简记为$\alpha_1\Rightarrow ^n\alpha_n$。  </p>
<ul>
<li>$\alpha\Rightarrow ^0\alpha$</li>
<li>$\Rightarrow ^+$表示“<code>经过正数步推导</code>”</li>
<li>$\Rightarrow ^{*}$表示“<code>经过若干（可以是0）步推导</code>”</li>
</ul>
<p>例：<br>$$<br>\begin{array}{l}<br>&lt;句子&gt;&amp;\Rightarrow&lt;名词短语&gt;&lt;动词短语&gt;\\<br>&amp;\Rightarrow&lt;形容词&gt;&lt;名词短语&gt;\\<br>&amp;\Rightarrow&lt;名词&gt;\\<br>&amp;\Rightarrow&lt;动词&gt;&lt;名词短语&gt;\\<br>&amp;\Rightarrow little\\<br>&amp;\Rightarrow boy\\<br>&amp;\Rightarrow apple\\<br>&amp;\Rightarrow eat<br>\end{array}<br>$$<br><span class="suojin"></span>自上向下就叫推导，反之则是规约</p>
<h3 id="回答前面的问题"><a href="#回答前面的问题" class="headerlink" title="回答前面的问题"></a>回答前面的问题</h3><p>$$<br>\left.<br>\begin{array}{l}<br>\text{句子的推导（派生）}&amp;\text{——从生成语言的角度}\\<br>\text{句子的归约}&amp;\text{——从识别语言的角度}<br>\end{array}<br>\right\}<br>\mathtt{均根据规则}<br>$$</p>
<h3 id="句型和句子"><a href="#句型和句子" class="headerlink" title="句型和句子"></a>句型和句子</h3><ul>
<li>如果$S\Rightarrow^{*}\alpha,\alpha\in (V_T\cup V_N)^{*}$，则称$\alpha$是$G$的一个<code>句型</code>($sentential\ form$)<ul>
<li>一个句型可能既包含<code>终结符</code>又包含<code>非终结符</code>，也可能是<code>空串</code></li>
</ul>
</li>
<li>如果$S\Rightarrow^{*}\omega,\omega\in V_T^{*}$，则称$\omega$是$G$的一个<code>句子</code>($sentence$)<ul>
<li>句子是不包含<code>非终结符</code>的<code>句型</code></li>
</ul>
</li>
</ul>
<p>例：<br>$$<br>\left.<br>\begin{array}{l}<br>&lt;句子&gt;&amp;\Rightarrow&lt;名词短语&gt;&lt;动词短语&gt;\ \ \ \ \ \ \ \ \ \\<br>&amp;\Rightarrow&lt;形容词&gt;&lt;名词短语&gt;&lt;动词短语&gt;\ \ \ \ \ \ \ \ \ \ \ \ \\<br>&amp;\Rightarrow little&lt;名词短语&gt;&lt;动词短语&gt;\\<br>&amp;\Rightarrow little&lt;名词&gt;&lt;动词短语&gt;\\<br>&amp;\Rightarrow little\ boy\ &lt;动词短语&gt;\\<br>&amp;\Rightarrow little\ boy\ &lt;动词&gt;&lt;名词短语&gt;\\<br>&amp;\Rightarrow little\ boy\ eats\ &lt;名词短语&gt;\\<br>&amp;\Rightarrow little\ boy\ eats\ &lt;名词&gt;\\<br>&amp;\Rightarrow \underbrace{little\ boy\ eats\ apple}_{句子}<br>\end{array}<br>\right\}<br>句型<br>$$</p>
<h3 id="语言的形式化定义"><a href="#语言的形式化定义" class="headerlink" title="语言的形式化定义"></a>语言的形式化定义</h3><p><span class="suojin"></span>由文法$G$的开始符号$S$推导出的所有句子构成的集合称为<code>文法G生成的语言</code>，记为$L(G)$。即<br>$$<br>L(G)=\lbrace \omega\mid S\Rightarrow^{*}\omega,\omega\in V_T^{*} \rbrace<br>$$</p>
<p>例：<br>文法$G$</p>
<ul>
<li>$S\rightarrow L\mid LT$</li>
<li>$T\rightarrow L\mid D\mid TL\mid TD$</li>
<li>$L\rightarrow a\mid b\mid c\mid …\mid z$</li>
<li>$D\rightarrow 0\mid 1\mid 2\mid 3\mid …\mid 9$</li>
</ul>
<p><span class="suojin"></span>该文法生成的语言是：<code>标识符</code>  </p>
<h3 id="语言上的运算"><a href="#语言上的运算" class="headerlink" title="语言上的运算"></a>语言上的运算</h3><table>
<thead>
<tr>
<th>运算</th>
<th>定义和表示</th>
</tr>
</thead>
<tbody>
<tr>
<td>$L$和$M$的并</td>
<td>$L\cup M=\lbrace s\mid s\in L \ &#124;&#124;\ s\in M\rbrace$</td>
</tr>
<tr>
<td>$L$和$M$的连接</td>
<td>$LM=\lbrace st\mid s\in L \ \&amp;\&amp;\ t\in M\rbrace$</td>
</tr>
<tr>
<td>$L$的幂</td>
<td>$\begin{cases}L^0=\lbrace\epsilon\rbrace\\L^n=L^{n-1}L, &amp; n \geqslant 1\end{cases}$</td>
</tr>
<tr>
<td>$L$的$Kleene$闭包</td>
<td>$L^{*}=\cup ^\infty_{i=0}L^i$</td>
</tr>
<tr>
<td>$L$的正闭包</td>
<td>$L^{+}=\cup ^\infty_{i=0}L^i$</td>
</tr>
</tbody>
</table>
<p>例：令$L=\lbrace A,B,…,Z,a,b,…,z\rbrace,D=\lbrace 0,1,…,9\rbrace$。<br>则$L(L\cup D)^{*}$表示的语言是<code>标识符</code>。</p>
<h2 id="文法的分类"><a href="#文法的分类" class="headerlink" title="文法的分类"></a>文法的分类</h2><p>$Chomsky$文法分类体系</p>
<ul>
<li>$0$型文法 ($Type-0\ Grammar$)</li>
<li>$1$型文法 ($Type-1\ Grammar$)</li>
<li>$2$型文法 ($Type-2\ Grammar$)</li>
<li>$3$型文法 ($Type-3\ Grammar$)</li>
</ul>
<h3 id="0-型文法-Type-0-Grammar"><a href="#0-型文法-Type-0-Grammar" class="headerlink" title="$0$型文法 ($Type-0\ Grammar$)"></a>$0$型文法 ($Type-0\ Grammar$)</h3><p>$$\alpha\rightarrow\beta$$ </p>
<ul>
<li><code>无限制文法</code>($Unrestricted\ Grammar$)/<code>短语结构文法</code>($Phrase\ Structure Grammar,PSG$)  <ul>
<li>$\forall\alpha\rightarrow\beta\in P$，$\alpha$中至少包含$1$个非终结符  </li>
</ul>
</li>
<li><code>0型语言</code><ul>
<li>由$0$型文法$G$生成的语言$L(G)$</li>
</ul>
</li>
</ul>
<h3 id="1-型文法-Type-1-Grammar"><a href="#1-型文法-Type-1-Grammar" class="headerlink" title="$1$型文法 ($Type-1\ Grammar$)"></a>$1$型文法 ($Type-1\ Grammar$)</h3><p>$$\alpha\rightarrow\beta$$ </p>
<ul>
<li><code>上下文有关文法</code>($Context-Sensitive\ Grammar,CSG$)<ul>
<li>$\forall\alpha\rightarrow\beta\in P,\mid\alpha\mid\leqslant\mid\beta\mid$</li>
<li>产生式的一般形式： $\alpha_1A\alpha_2\rightarrow\alpha_1\beta\alpha_2(\beta\ne\epsilon)$</li>
</ul>
</li>
<li><code>上下文有关语言（1型语言）</code><ul>
<li>上下文有关文法 ($1$型文法)$G$生成的语言$L(G)$</li>
</ul>
</li>
</ul>
<blockquote>
<p>CSG中不包含$\epsilon-$产生式</p>
</blockquote>
<h3 id="2-型文法-Type-2-Grammar"><a href="#2-型文法-Type-2-Grammar" class="headerlink" title="$2$型文法 ($Type-2\ Grammar$)"></a>$2$型文法 ($Type-2\ Grammar$)</h3><p>$$\alpha\rightarrow\beta$$ </p>
<ul>
<li><code>上下文无关文法</code>($Context-Free\ Grammar,CFG$)<ul>
<li>$\forall\alpha\rightarrow\beta\in P,\alpha\in V_N$</li>
<li>产生式的一般形式：$A\rightarrow\beta$</li>
<li>例：$S\rightarrow L\mid LT\\T\rightarrow L\mid D\mid TL\mid TD\\L\rightarrow a\mid b\mid c\mid d\mid …\mid z\\D\rightarrow 0\mid 1\mid 2\mid 3\mid …\mid 9$</li>
</ul>
</li>
<li><code>上下文无关语言（2型语言）</code><ul>
<li>由上下文无关文法 ($2$型文法)$G$生成的语言$L(G)$ </li>
</ul>
</li>
</ul>
<h3 id="3-型文法-Type-3-Grammar"><a href="#3-型文法-Type-3-Grammar" class="headerlink" title="$3$型文法 ($Type-3\ Grammar$)"></a>$3$型文法 ($Type-3\ Grammar$)</h3><p>$$\alpha\rightarrow\beta$$ </p>
<ul>
<li>正则文法($Regular\ Grammar,RG$)<ul>
<li>右线性($Right\ Linear$)文法：$A\rightarrow\omega B&#124;&#124;A\rightarrow\omega$ </li>
<li>左线性($Left\ Linear$)文法：$A\rightarrow B\omega &#124;&#124;A\rightarrow\omega$ </li>
<li>左线性文法和右线性文法都称为正则文法</li>
</ul>
</li>
<li><code>正则语言（3型语言）</code><ul>
<li>由正则文法($3$型文法)$G$生成的语言$L(G)$</li>
</ul>
</li>
</ul>
<p>例（右线性文法）：</p>
<ul>
<li>$S\rightarrow a\mid b\mid c\mid d$</li>
<li>$S\rightarrow aT\mid bT\mid cT\mid dT$</li>
<li>$T\rightarrow a\mid b\mid c\mid d\mid 1\mid 2\mid 3\mid 4\mid 5$</li>
<li>$T\rightarrow aT\mid bT\mid cT\mid dT\mid 1T\mid 2T\mid 3T\mid 4T\mid 5T$</li>
</ul>
<blockquote>
<p>正则文法能描述程序设计语言的多数单词</p>
</blockquote>
<h3 id="四种文法之间的关系"><a href="#四种文法之间的关系" class="headerlink" title="四种文法之间的关系"></a>四种文法之间的关系</h3><ul>
<li>逐级限制<ul>
<li>$0$型文法：$\alpha$中至少包含$1$个非终结符</li>
<li>$1$型文法（$CSG$）：$\mid\alpha\mid\leqslant\mid\beta\mid$</li>
<li>$2$型文法（$CFG$）：$\alpha\in V_N$</li>
<li>$3$型文法（$RG$）：$A\rightarrow\omega B&#124;&#124;A\rightarrow\omega(A\rightarrow B\omega &#124;&#124;A\rightarrow\omega)$</li>
</ul>
</li>
<li>逐级包含<ul>
<li>$3$型文法$\subseteq2$型文法$\subseteq1$型文法$\subseteq0$型文法</li>
</ul>
</li>
</ul>
<h2 id="CFG-的语法分析树"><a href="#CFG-的语法分析树" class="headerlink" title="$CFG$的语法分析树"></a>$CFG$的语法分析树</h2><ul>
<li><code>根节点</code>的标号为<code>文法开始符号</code></li>
<li><code>内部结点</code>表示对一个产生式$A\rightarrow\beta$的应用，该<code>结点的标号</code>是此产生式<code>左部</code>$A$ 。该结点的<code>子结点的标号</code>从左到右构成了<code>产生式的右部</code>$\beta$。</li>
<li><code>叶结点</code>的标号既可以是<code>非终结符</code>，也可以是<code>终结符</code>。从左到右排列叶节点得到的符号串称为是这棵<code>树的产出</code>($yield$)或<code>边缘</code>($frontier$)。</li>
</ul>
<p>例：<br>$$E\rightarrow E+E\\E\rightarrow E*E\\E\rightarrow (E)\\E\rightarrow id$$<br>的语法分析树为：</p>
<p><link rel="stylesheet" href="/css/Treant.css" type="text/css"></p>
<p><link rel="stylesheet" href="/css/super-simple.css"></p>
<script src="/js/raphael-tree.js"></script>
<script src="/js/Treant.js"></script>
<div class="chart" id="OrganiseChart-simple-1"></div>
<script>
var simple_chart_config_1 = {
    chart: { container: "#OrganiseChart-simple-1", connectors: { type: 'straight' } },
    nodeStructure: {
        text: { name: "$E$" },
        children: [
            { text: { name: "$-$" } },
            { 
                text: { name: "$E$" }, 
                children: [
                    { text: { name: "$($" } },
                    { 
                        text: { name: "$E$" },
                        children: [
                            { text: { name: "$E$" } },
                            { text: { name: "$+$" } },
                            { text: { name: "$E$" } }
                        ] 
                    },
                    { text: { name: "$)$" } }
                ]
            }
        ]
    }
};

    new Treant( simple_chart_config_1 );
</script>

<h3 id="分析树是推导的图形化表示"><a href="#分析树是推导的图形化表示" class="headerlink" title="分析树是推导的图形化表示"></a>分析树是推导的图形化表示</h3><p><span class="suojin"></span>给定一个推导$S\Rightarrow\alpha_1\Rightarrow\alpha_2\Rightarrow…\Rightarrow\alpha_{n}$，对于推导过程中得到的每一个<code>句型</code>$\alpha_{i}$，都可以构造出一个边缘为$\alpha_{i}$的<code>分析树</code>。</p>
<h3 id="二义性文法-Ambiguous-Grammar"><a href="#二义性文法-Ambiguous-Grammar" class="headerlink" title="二义性文法($Ambiguous\ Grammar$)"></a>二义性文法($Ambiguous\ Grammar$)</h3><p><span class="suojin"></span>如果一个文法可以为某个句子生成<code>多棵分析树</code>，则称这个文法是<code>二义性</code>的。<br>例：  </p>
<ul>
<li>文法<ul>
<li>$\left.\begin{array}{l}stmt\rightarrow &amp;\text{if}\ expr\ \text{then}\ stmt\\&amp;&#124;\text{if}\ expr\ \text{then}\ stmt\ \text{else}\ stmt\end{array}\right\}条件语句\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ &#124;\text{other}\longleftarrow其他语句<br>$</li>
</ul>
</li>
<li>句型<ul>
<li>$\text{if}\ E_1\ \text{then}\ \underline{\underline{\text{if}\ E_2\ \text{then}\ S_1}\ \text{else}\ S_2}$</li>
</ul>
</li>
</ul>
<p><div class="chart" id="OrganiseChart-simple-2"></div></p>
<script>
var simple_chart_config_2 = {
    chart: { container: "#OrganiseChart-simple-2", connectors: { type: 'straight' } },
    nodeStructure: {
        text: { name: "$stmt$" },
        children: [
            { text: { name: "if" } },
            { text: { name: "$expr(E1)$" } },
            { text: { name: "then" } },
            { 
                text: { name: "$stmt$" }, 
                children: [
                    { text: { name: "if" } },
                    { text: { name: "$expr(E2)$" } },
                    { text: { name: "then" } },
                    { text: { name: "$stmt(S1)$" } },
                    { text: { name: "else" } },
                    { text: { name: "$stmt(S2)$" } }
                ]
            }
        ]
    }
};

    new Treant( simple_chart_config_2 );
</script>

<p>$$树\ 1$$</p>
<p><div class="chart" id="OrganiseChart-simple-3"></div></p>
<script>
var simple_chart_config_3 = {
    chart: { container: "#OrganiseChart-simple-3", connectors: { type: 'straight' } },
    nodeStructure: {
        text: { name: "$stmt$" },
        children: [
            { text: { name: "if" } },
            { text: { name: "$expr(E1)$" } },
            { text: { name: "then" } },
            { 
                text: { name: "$stmt$" }, 
                children: [
                    { text: { name: "if" } },
                    { text: { name: "$expr(E2)$" } },
                    { text: { name: "then" } },
                    { text: { name: "$stmt(S1)$" } },
                ]
            },
            { text: { name: "else" } },
            { text: { name: "$stmt(S2)$" } }
        ]
    }
};

    new Treant( simple_chart_config_3 );
</script>

<p>$$树\ 2$$</p>
<blockquote>
<p>消歧规则：每个$else$和最近的尚未匹配的$if$匹配，故树$1$正确。</p>
</blockquote>
<h3 id="二义性文法的判定"><a href="#二义性文法的判定" class="headerlink" title="二义性文法的判定"></a>二义性文法的判定</h3><ul>
<li>对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组<code>充分条件</code>，满足这组充分条件的文法是无二义性的<ul>
<li>满足，肯定无二义性</li>
<li>不满足，也未必就是有二义性的</li>
</ul>
</li>
</ul>

      
    </div>
    
  </div>
  
	<! -- 添加打赏功能 -->
<div class ="post-donate">
    <div id="donate_board" class="donate_bar center">
        <a id="btn_donate" class="btn_donate" href="javascript:;" title="打赏">￥打赏</a><span class="donate_txt">赞助吃土少年！￣﹃￣</span>
    </div>  
	<div id="donate_guide" class="donate_bar center hidden" >
		<!-- 支付宝打赏图案 --><img src="/img/zhifubaodonate.png" alt="支付宝打赏" /> 
		<!-- 微信打赏图案 --><img src="/img/weixindonate.png" alt="微信打赏" />  
    </div>
	<script type="text/javascript">
		document.getElementById('btn_donate').onclick = function(){
			$('#donate_board').addClass('hidden');
			$('#donate_guide').removeClass('hidden');
		}
	</script>
</div>
  
  
    
    <div class="copyright">
        <p><span>本文标题:</span><a href="/2016/11/30/Compile02/">编译原理——语言及其文法</a></p>
        <p><span>文章作者:</span><a href="/" title="回到主页">Shawn</a></p>
        <p><span>本文字数:</span><span class="post-count">2,930字</span></p>
        <p><span>发布时间:</span>2016-11-30, 15:44:36</p>
        <p><span>最后更新:</span>2016-12-30, 18:57:08</p>
        <p>
            <span>原始链接:</span><a class="post-url" href="/2016/11/30/Compile02/" title="编译原理——语言及其文法">http://shawnzeng.com/2016/11/30/Compile02/</a>
            <span class="copy-path" data-clipboard-text="原文: http://shawnzeng.com/2016/11/30/Compile02/　　作者: Shawn" title="点击复制文章链接"><i class="fa fa-clipboard"></i></span>
            <script> var clipboard = new Clipboard('.copy-path'); </script>
        </p>
        <p>
            <span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
        </p>
    </div>



    <nav id="article-nav">
        
            <div id="article-nav-newer" class="article-nav-title">
                <a href="/2016/12/01/Yoga/">
                    林宥嘉：她说好
                </a>
            </div>
        
        
            <div id="article-nav-older" class="article-nav-title">
                <a href="/2016/11/30/Compile01/">
                    编译原理——简介
                </a>
            </div>
        
    </nav>

  
  
</article>

    <div id="toc" class="toc-article">
        <strong class="toc-title">文章目录</strong>
        
            <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#基本概念"><span class="toc-number">1.</span> <span class="toc-text">基本概念</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#字母表"><span class="toc-number">1.1.</span> <span class="toc-text">字母表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#字母表上的运算"><span class="toc-number">1.1.1.</span> <span class="toc-text">字母表上的运算</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#串"><span class="toc-number">1.2.</span> <span class="toc-text">串</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#串上的运算"><span class="toc-number">1.3.</span> <span class="toc-text">串上的运算</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#文法的定义"><span class="toc-number">2.</span> <span class="toc-text">文法的定义</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#文法的形式化定义"><span class="toc-number">2.1.</span> <span class="toc-text">文法的形式化定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#产生式的简写"><span class="toc-number">2.2.</span> <span class="toc-text">产生式的简写</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#符号约定"><span class="toc-number">2.3.</span> <span class="toc-text">符号约定</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#语言的定义"><span class="toc-number">3.</span> <span class="toc-text">语言的定义</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#推导-Derivations-和归约-Reductions"><span class="toc-number">3.1.</span> <span class="toc-text">推导($Derivations$)和归约($Reductions$)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#回答前面的问题"><span class="toc-number">3.2.</span> <span class="toc-text">回答前面的问题</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#句型和句子"><span class="toc-number">3.3.</span> <span class="toc-text">句型和句子</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#语言的形式化定义"><span class="toc-number">3.4.</span> <span class="toc-text">语言的形式化定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#语言上的运算"><span class="toc-number">3.5.</span> <span class="toc-text">语言上的运算</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#文法的分类"><span class="toc-number">4.</span> <span class="toc-text">文法的分类</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#0-型文法-Type-0-Grammar"><span class="toc-number">4.1.</span> <span class="toc-text">$0$型文法 ($Type-0\ Grammar$)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-型文法-Type-1-Grammar"><span class="toc-number">4.2.</span> <span class="toc-text">$1$型文法 ($Type-1\ Grammar$)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-型文法-Type-2-Grammar"><span class="toc-number">4.3.</span> <span class="toc-text">$2$型文法 ($Type-2\ Grammar$)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-型文法-Type-3-Grammar"><span class="toc-number">4.4.</span> <span class="toc-text">$3$型文法 ($Type-3\ Grammar$)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#四种文法之间的关系"><span class="toc-number">4.5.</span> <span class="toc-text">四种文法之间的关系</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#CFG-的语法分析树"><span class="toc-number">5.</span> <span class="toc-text">$CFG$的语法分析树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#分析树是推导的图形化表示"><span class="toc-number">5.1.</span> <span class="toc-text">分析树是推导的图形化表示</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#二义性文法-Ambiguous-Grammar"><span class="toc-number">5.2.</span> <span class="toc-text">二义性文法($Ambiguous\ Grammar$)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#二义性文法的判定"><span class="toc-number">5.3.</span> <span class="toc-text">二义性文法的判定</span></a></li></ol></li></ol>
        
    </div>
    <style>
        .left-col .switch-btn,
        .left-col .switch-area {
            display: none;
        }
        .toc-level-3 i,
        .toc-level-3 ol {
            display: none !important;
        }
    </style>

    <input type="button" id="tocButton" value="隐藏目录"  title="点击按钮隐藏或者显示文章目录">

    <script>
        yiliaConfig.toc = ["隐藏目录", "显示目录", !!"false"];
    </script>



    <div class="share">
    
        <div class="bdsharebuttonbox">
            <a href="#" class="fa fa-twitter bds_twi" data-cmd="twi" title="分享到推特"><span class=""></a>
            <a href="#" class="fa fa-weibo bds_tsina" data-cmd="tsina" title="分享到新浪微博"></a>
            <a href="#" class="fa fa-qq bds_sqq" data-cmd="sqq" title="分享给 QQ 好友"></a>
            <a href="#" class="fa fa-files-o bds_copy" data-cmd="copy" title="复制网址"></a>
            <a href="#" class="fa fa fa-envelope-o bds_mail" data-cmd="mail" title="通过邮件分享"></a>
            <a href="#" class="fa fa-weixin bds_weixin" data-cmd="weixin" title="生成文章二维码"></a>
            <a href="#" class="fa fa-share-alt bds_more" data-cmd="more"></i></a>
        </div>
       <script>
            window._bd_share_config={
                "common":{"bdSnsKey":{},"bdText":"编译原理——语言及其文法　| 诗酒趁年华　","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='//bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
        </script>
    

    
</div>







    
      <div class="duoshuo" id="comments">
    <div id="comment-box" ></div>
    <div class="ds-thread" id="ds-thread" data-thread-key="2016/11/30/Compile02/" data-title="编译原理——语言及其文法" data-url="http://shawnzeng.com/2016/11/30/Compile02/"></div>
    <script type="text/javascript">
        var duoshuoQuery = {short_name:"zengshuai1996"};
        var loadComment = function(){
            var d = document, s = d.createElement('script');
            //s.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//shawnzeng.com/js/embed.js';
            s.src = '/js/embed.js';
            s.async = true; s.charset = 'UTF-8';
            (d.head || d.body).appendChild(s);
        }

        
    </script>
    
    <script> loadComment(); </script>

</div>
    




    <div class="scroll" id="post-nav-button">
        
            <a href="/2016/12/01/Yoga/" title="上一篇: 林宥嘉：她说好">
                <i class="fa fa-angle-left"></i>
            </a>
        

        <a title="文章列表"><i class="fa fa-bars"></i><i class="fa fa-times"></i></a>

        
            <a href="/2016/11/30/Compile01/" title="下一篇: 编译原理——简介">
                <i class="fa fa-angle-right"></i>
            </a>
        
    </div>

    <ul class="post-list"><li class="post-list-item"><a class="post-list-link" href="/2017/04/14/StopHexo/">停止更新</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/30/Https/">腾讯云Centos7启用https</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/25/AddBaiduCDN/">给自己的博客添加CDN加速</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/18/NightMode/">给自己的主题添加夜间模式</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/13/2017hanjiaplan/">2017寒假计划get√！</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/13/PSPic/">使用PS压缩背景图</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/10/Algorithm-homework/">算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/31/Hi2017/">2017新年快乐！</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/30/HuaJi/">滑稽大盗</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/27/Serviceology02/">服务学作业——堆糖电商服务建模</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/14/Compile_SubsetConstruction_Algorithm/">编译原理——子集构造法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/05/HexoStudy/">Hexo学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/05/AddUML/">给hexo添加uml时序图和流程图功能</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/03/YourName/">「君の名は。」</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/01/Yoga/">林宥嘉：她说好</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/30/Compile02/">编译原理——语言及其文法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/30/Compile01/">编译原理——简介</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/28/SDAPM-Scope-Statement/">Software Development And Project Management Homework——Scope Statement</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/28/SDAPM-Project-Charter/">Software Development And Project Management Homework——Project Charter</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/05/RestartBlog/">重头再来:Mac上搭建基于GitHub的Hexo博客</a></li></ul>




    <script>
        
    </script>
</div>
      			<footer id="footer">
    <div class="outer">
        <div id="footer-info">
            <div class="footer-left">
                <i class="fa fa-copyright"></i> 
                2016-2017 <i class="fa fa-heart animated infinite pulse"></i> Shawn <a href="http://www.miitbeian.gov.cn">黑ICP备17000197号-1</a>
            </div>
            <div class="footer-right">
            	<span class="my-face">(●'◡'●)ﾉ</span>
				<span id="span_dt_dt"></span>
            </div>
        </div>
        
            <div class="visit">
                
                    <span id="busuanzi_container_site_pv" style='display:none'>
                        <span id="site-visit" title="本站到访数"><i class="fa fa-user" aria-hidden="true"></i><span id="busuanzi_value_site_uv"></span>
                        </span>
                    </span>
                
                
                    <span>| </span>
                
                
                    <span id="busuanzi_container_page_pv" style='display:none'>
                        <span id="page-visit"  title="本页阅读量"><i class="fa fa-eye animated infinite pulse" aria-hidden="true"></i><span id="busuanzi_value_page_pv"></span>
                        </span>
                    </span>
                
            </div>
        
    </div>
</footer>

    		</div>
    		<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


    <script src="/js/raphael.js"></script>
    <script src="/js/underscore.js"></script>
    <script src="/js/sequence-diagram.js"></script>
    <script src="/js/flowchart.js"></script>
    
<!-- Chart Render -->
<script type="text/javascript">
  $(".sequence").sequenceDiagram({theme: 'simple'});
  var flowCount = 0;
  $(".flow").each(function() {
      var el = $(this);
      el.hide();
      el.after('<div id="flow-' + flowCount + '"></div>');
      var chart = flowchart.parse(el.text());
      chart.drawSVG('flow-' + flowCount);
      flowCount++;
  });
</script>
<!-- End Chart Render -->


<script data-main="/js/main.js" src="//cdn.bootcss.com/require.js/2.2.0/require.min.js"></script>

    <script>
        $(document).ready(function() {
            var iPad = window.navigator.userAgent.indexOf('iPad');
            if (iPad > -1 || $(".left-col").css("display") === "none") {
                var bgColorList = ["#9db3f4", "#414141", "#e5a859", "#f5dfc6", "#c084a0", "#847e72", "#cd8390", "#996731"];
                var bgColor = Math.ceil(Math.random() * (bgColorList.length - 1));
                $("body").css({"background-color": bgColorList[bgColor], "background-size": "cover"});
            }
            else {
                var backgroundnum = 5;
                var backgroundimg = "url(/background/bg-x.jpg)".replace(/x/gi, Math.ceil(Math.random() * backgroundnum));
                $("body").css({"background": backgroundimg, "background-attachment": "fixed", "background-size": "cover"});
            }
        })
    </script>





    <script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {
    inlineMath: [['$','$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
	linebreaks: { automatic: true, width: "container" }
  }
});

MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';                 
    }       
});
</script>

<!--script type="text/javascript" src="http://mathjax.josephjctang.com/MathJax.js?config=TeX-MML-AM_HTMLorMML"-->
<!--script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"-->
<script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_HTMLorMML">
</script>


<div class="scroll" id="scroll">
    <a href="#" title="返回顶部"><i class="fa fa-arrow-up"></i></a>
    <a href="#comments" onclick="load$hide();" title="查看评论"><i class="fa fa-comments-o"></i></a>
    <a href="#footer" title="转到底部"><i class="fa fa-arrow-down"></i></a>
</div>
<script>
    // Open in New Window
    
        var oOpenInNew = {
            
            
            
            
            
            
            
             miniArchives: "a.post-list-link", 
            
             friends: "#js-friends a", 
             socail: ".social a" 
        }
        for (var x in oOpenInNew) {
            $(oOpenInNew[x]).attr("target", "_blank");
        }
    
</script>

    <script>
        var originTitle = document.title;
        var titleTime;
        document.addEventListener("visibilitychange", function() {
            if (document.hidden) {
                document.title = "(つェ⊂)" + originTitle;
                clearTimeout(titleTime);
            }
            else {
                document.title = "(*´∇｀*)" + originTitle;
                titleTime = setTimeout(function() {
                    document.title = originTitle;
                }, 2000);
            }
        })
    </script>

<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    		<div class="musicbox">
				<div class="player">
					<div id="player_bck" class="aplayer"></div>
				</div>
				<div class="pop-music" title="音乐"></div>
			</div>
  		</div>
  		<script src="/js/music.js"></script>
	</body>	
</html>